2017-07-08

算法设计与分析[0022] BST（二叉查找树）和 R-B Tree（红黑树）

　一些计算机程序设计中常用的线性数据结构：Array、ArrayList、LinkedList、List、Stack、Queue、Hashtable 和Dictionary。为了更高效的进行数据的查找和访问，例如避免普通数据查找的 $O(N)$ 线性时间复杂度，常用树这种数据结构保存数据。
　树（Tree）是由多个节点（Node）的集合组成，每个节点又有多个与其关联的子节点（Child Node）；子节点就是直接处于节点之下的节点，而父节点（Parent Node）则位于节点直接关联的上方；树的根（Root）指的是一个没有父节点的单独的节点。所有的树都呈现了一些共有的性质：①只有一个根节点；②除了根节点，所有节点都有且只有一个父节点；③无环。将任意一个节点作为起始节点，都不存在任何回到该起始节点的路径（正是前两个性质保证了无环的成立）。
　更高效同时也相对更加复杂的树型数据结构包括 BST（二叉查找树）、R-B Tree（红黑树）、AVL Tree（平衡二叉树：父节点的左子树和右子树的高度之差不能大于1）、Treap（树堆：满足①二叉查找树的性质；满足②堆的性质）、Splay Tree（伸展树：在一次搜索后，会对树进行一些特殊的操作，这些操作的理念与AVL树有些类似，即通过旋转，来改变树节点的分布，并减小树的深度；伸展树并没有AVL树的平衡要求，任意节点的左右子树可以相差任意深度）、B-Tree（B树：多叉平衡查找树，B$^{+}$-Tree（B+树）是B树的变体）等。
　本文主要介绍基础的 BST（二叉查找树）以及提升搜索效率的更高级的数据结构：R-B Tree（红黑树）。

二叉查找树

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree），排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树
- 若任意节点的左子树不空，则左子树上所有结点的值均不大于它的根结点的值
- 若任意节点的右子树不空，则右子树上所有结点的值均不小于它的根结点的值
- 任意节点的左、右子树也分别为二叉查找树
二叉查找树的一般结构：

struct TreeNode {
  // 节点关键字
  int key;
  // 节点卫星数据
  type val;
  // 指向父节点
  TreeNode* parent;
  // 指向左子树
  TreeNode* left;
  // 指向右子树
  TreeNode* right;
  TreeNode(int key): key(key), val(NULL), parent(NULL), left(NULL), right(NULL) {}
};

查询二叉查找树

　查询某元素、最大最小节点、前驱后继节点。

查询某元素
- 在二叉查找树中查询某个元素k
  - 若k大于当前节点关键字，则搜索其右子树；
  - 若k小于当前节点关键字，则搜索其左子树；
  - 若k等于当前节点关键字或者当前节点为空，返回当前节点。

递归版本

//输入：node二叉查找树的根节点，k为待查找元素
//输出：查找到的对应节点
Tree-Search(node, k)
  if(node==NULL || k==node->key)
    return node;
  if(k < node->key)
    return Tree-Search(node->left, k);
  else
    return Tree-Search(node->right, k);

非递归版本

//输入：node二叉查找树的根节点，k为待查找元素
//输出：查找到的对应节点
Tree-Search(node, k)
  while(node!=NULL && k!=node->key) {
    if(k < node->key)
      node = node->left;
    else
      node = node->right;
  }
  return node;

查询最大最小节点
- 最大节点：二叉查找树最右侧节点
- 最小节点：二叉查找树最左侧节点

Tree-Minimum(node)
  while(node->left != NULL)
    node = node->left;
  return node;
 
Tree-Maximum(node)
  while(node->right != NULL)
    node = node->right;
  return node;

查询前驱后继节点
- 后继：指关键字大于某节点key[x]的所有节点中，关键字最小的节点，即对树进行中序遍历，紧随其后的节点。
- 前驱：小于某节点key[x]的关键字中最大的那个节点，即树的中序遍历中，排在其前的节点。
- 求某个节点的后继节点分为三种情况：
  - 该节点有右子树，则其后继节点是其右子树的最左侧节点，即右子树的最小节点。
  - 该节点无右子树，但是父节点的左孩子，则该节点的后继节点是该父节点。
  - 该节点无右子树，且是父节点的右孩子，则需要一直向上搜索，直到它的n-1代祖先是它第n代祖先的左孩子，则它的后继就是第n个祖先。如果一直搜索到根节点，也没有找到n-1代祖先是它第n代祖先的左孩子，则该节点是整个树的中序遍历中的最后一个节点，即它没有后继。

Tree-Successor(node)
  if(node->right != NULL)
    return Tree-Minimum(node->right)
  //x用来保存待确定的节点
  //y为x的父节点
  x = node;
  TreeNode y = x->parent;
  // x==y->right <==> x!=y->left
  while(y!=NULL && x==y->right)
    x = y;
    y = x->parent;
 
  return y;

求某个节点的前驱节点与求后继节点类似：
- 该节点有左子树，则其前驱节点是其左子树的最右侧节点，即左子树的最大节点。
- 该节点无左子树，但是父节点的右孩子，则该节点的前驱节点是该父节点。
- 该节点无左子树，且是父节点的左孩子，则需要一直向上搜索，直到它的n-1代祖先是它第n代祖先的右孩子，则它的后继就是第n个祖先。如果一直搜索到根节点，也没有找到n-1代祖先是它第n代祖先的右孩子，则该节点是整个树的中序遍历中的第一个节点，即它没有前驱。

Tree-Predecessor(node)
  if(node->left != NULL)
    return Tree-Maximum(node->right)
  //x用来保存待确定的节点
  //y为x的父节点
  x = node;
  TreeNode y = x->parent;
  // x==y->left <==> x!=y->right
  while(y!=NULL && x==y->left)
    x = y;
    y = x->parent;
 
  return y;

插入和删除

　插入和删除需要在保持二叉查找树性质的情况下，对树进行修改。

插入
- 若为空树，则直接将插入的节点作为根节点；
- 若插入节点关键字小于当前节点关键字，应插入在当前节点左子树中；否则应插入在右子树中；
- 直到当前节点为叶子节点，则将插入节点变成当前节点的左孩子或右孩子。

Tree-Insert(root, node)
  curNode = root
  leafNode = NULL
  while(curNode != NULL)
    leafNode = curNode
    if(node->key >= curNode->key)
      curNode = curNode->right
    else
      curNode = curNode->left
 
  node->parent = leafNode
  // 当前树为空树
  if(leafNode==NULL)
    root = node
  else
    if(node->key >= leafNode->key)
      leafNode->right = node
    else
      leafNode->left = node

删除
- 相比插入，删除操作较为复杂。删除操作分为三种情况：
  - 若删除节点为叶子节点（没有左右子树），此时删除该节点不会破坏二叉查找树的结构，则直接将其删除；
  - 若删除节点只有一个子节点，则用子节点替代删除节点的位置（直接删除该节点，并将其左子树或者右子树设置为其父节点的左子树或者右子树即可，此操作不会破坏二叉查找树的结构），此时该子节点称为“替代节点”；
  - 若删除节点有两个子节点，一般的删除策略是用其右子树的最小数据（容易找到）代替要删除的节点数据，并删除该节点（此时为NULL）：因为右子树的最小节点不可能有左孩子，所以第二次删除较为容易。
    - 右子树的最小数据即为当前节点的后继节点，$z$ 的左子树和右子树均不空，找到 $z$ 的后继 $y$，用 $y$ 的值代替 $z$ 的值；因为 $y$ 一定没有左子树，所以可以删除 $y$，并让 $y$ 的父亲节点成为 $y$ 的右子树的父亲节点。

Tree-Delete(root, node)
  curNode = root;
  parent = NULL;
  while(NULL != node) {
    if(node->key < curNode->key) {
      parent = curNode;
      curNode = curNode->left;
    }
    else if(node->key > curNode->key) {
      parent = curNode;
      curNode = curNode->right;
    }
    // found
    else {
      // 叶子节点
      if(NULL==curNode->left && NULL==curNode->right) {
        // 根结点
        if(parent == NULL) { 
          delete curNode;
          curNode = NULL;
        }
        // 非根结点
        else {
          // 父节点的左子树部分还是右子树部分
          (parent->left==curNode)? (parent->left=NULL) : (parent->right=NULL);
          delete curNode;
          curNode = NULL;
        }
      }
      // 只有左孩子
      else if(NULL!=curNode->left && NULL==curNode->right) {
        if(parent == NULL) {
          TreeNode tmp = curNode;
          curNode = curNode->left;
          delete tmp;
          tmp = NULL; 
        }
        else {
          // 父节点的左子树部分还是右子树部分
          (parent->left==curNode)?(parent->left=curNode->left):(parent->right=curNode->left);
          delete curNode;
          curNode = NULL;
        }
      }
      // 只有右孩子
      else if(NULL==curNode->left && NULL!=curNode->right) {
        if(parent == NULL) {
          TreeNode tmp = curNode;
          curNode = curNode->right;
          delete tmp;
          tmp = NULL;
        }
        else {
          // 父节点的左子树部分还是右子树部分
          (parent->left==curNode)?(parent->left=curNode->right):(parent->right=curNode->right);
          delete curNode;
          curNode = NULL;
        }
      }
      // 既有左孩子又有右孩子
      else {
        TreeNode* rightNode = curNode;
        while(rightNode->left != NULL) {
          parent = rightNode;
          rightNode = rightNode->left;
        }
 
        // 交换rightNode与curNode
        int swapKey = rightNode->key;
        rightNode->key = curNode->key;
        curNode->key = swapKey;
 
        // 删除rightNode，parent肯定不为空
        // 后继节点没有右孩子
        if(NULL == rightNode->right) {
          parent->left = NULL
        }
        else {
          parent->left = rightNode->right;
        }
 
        delete rightNode;
        rightNode = NULL;
      }
    }
  }

满二叉树&完全二叉树

满二叉树（Full Binary Tree）
- 官方解释
  
  A full binary tree is a tree in which every node other than the leaves has two children.
- 总节点数 $k$：深度为 $h$，有 $k = 2^h - 1$
- 树高 $h$：$h = log_2 (k+1)$
完全二叉树（Complete Binary Tree）
- 官方解释
  
  A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
- 深度为 $h$，有 $n$ 个节点的二叉树，当且仅当其每一个节点都与深度为 $h$ 的满二叉树中，序号为 $1$ 至 $n$ 的节点对应时，为一棵完全二叉树。
- 总节点数 $k$：深度为 $h$，有 $2^{h-1} \leq k \lt 2^h - 1$
- 树高 $h$：$h = log_2 k + 1$

红黑树

　一棵由 $N$ 个节点的随机构造的二叉查找树的高度为 $logN$，所以顺理成章，二叉查找树的一般操作（主要是查找）的执行时间为 $O(logN)$。但二叉查找树若退化成了一棵具有 $N$ 个节点的线性链后，这些操作就变成最坏情况，运行时间变成 $O(N)$。
　红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的插入、删除、主要是查找的时间复杂度最坏为 $O(logN)$。

R-B Tree(Red-Black Tree)，它是一种特殊的二叉查找树，红黑树的每个节点除了包含key、left、right、parent外，还有存储位表示节点的颜色，可以是红(Red)或黑(Black)。但它是如何保证一棵 $N$ 个节点的红黑树的高度始终在 $logN$ 的呢？这就引出了红黑树的 5 个性质：
- ①每个节点不是黑色便是红色；
- ②根节点为黑色；
- ③每个叶子节点（即指树尾端那些空(NIL/NULL)的叶子节点）是黑色的；
- ④如果一个节点是红色的，则它的子节点（两个子节点）必须是黑色的（即从每个叶子节点到根的所有路径上不能有两个连续的红色节点）；
- ⑤从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
  - 对于任意节点而言，其到其子孙叶子节点树尾端NIL指针的每条路径都包含相同数目的黑节点。
  - 确保没有一条路径会比其它路径长出两个节点（一红一黑），因此，红黑树相对是接近平衡的二叉树。

　正是红黑树的这 5 条性质，使一棵 $N$ 个节点的红黑树始终保持了 $logN$ 的高度，也即“保证了红黑树的插入、删除、主要是查找的时间复杂度最坏为 $O(logN)$”。
　红黑树的应用比较广泛，主要用它来存储有序的数据，例如，Java 集合中的 TreeSet、TreeMap，C++ STL 中的 set、map，以及 Linux虚拟内存的管理，都是通过红黑树去实现的，它的时间复杂度是 $O(logN)$，效率非常之高。

红黑树的搜索时间复杂度

下面通过数学归纳法证明定理：一棵含有$N$个节点的红黑树的高度至多为$2log(N+1)$
- 转化为证明逆否命题
  
  “一棵含有 $N$ 个节点的红黑树的高度至多为 $2log(N+1)$” 的逆否命题是：”高度为 $h$ 的红黑树，它包含的节点个数至少为 $2^{h/2}$-1 个”。我们只需要证明逆否命题，即可证明原命题为真，即只需证明 “高度为 $h$ 的红黑树，它包含的节点个数至少为 $2^{h/2}$-1 个”。
- 从某个节点 $x$ 出发（不包括该节点）到达一个叶节点的任意一条路径上，黑色节点的个数称为该节点的黑高度(x’s black height)，记为 $bh(x)$。关于 $bh(x)$ 有两点需要说明：
  - 第1点：根据上述红黑树的性质⑤可知，从节点 $x$ 出发到达的所有的叶节点具有相同数目的黑节点，这也就意味着，$bh(x)$ 的值是唯一的！
  - 第2点：根据上述红黑树的性质④可知，从节点 $x$ 出发达到叶节点：$所经历的黑色节点数目 \geq 所经历的红节点的数目$。假设 $x$ 是根节点，则可以得出结论：$bh(x=root) \geq h/2$。进而，我们只需证明：“高度为 $h$ 的红黑树，它包含的黑色节点个数至少为 $2^{bh(x)}$-1个” 即可。
- “数学归纳法” 论证：“高度为 $h$ 的红黑树，它包含的黑色节点个数至少为 $2^{bh(x)}$-1个”
  - ①当树的高度 $h=0$ 时，节点个数是 0，$bh(x)$ 为 0，$2^{bh(x)}$-1 也为 0。显然，原命题成立。
  - ②当 $h \gt 0$，无妨设树的高度为 $h$-1 时，它包含的节点个数至少为 $2^{bh(x)-1}$-1。
    - 当树的高度为 $h$ 时，对于节点 $x$（$x$ 为根节点），其黑高度为 $bh(x)$；对于节点 $x$ 的左右子树，它们黑高度为 $bh(x)$ 或者 $bh(x)$-1；
    - 根据假设条件，我们已知 “$x$ 的左右子树，即高度为 $h$-1 的节点，它包含的节点至少为 $2^{bh(x)-1}$-1 个” ；
    - 所以，节点 $x$ 所包含的节点至少为：$(2^{bh(x)-1}-1) + (2^{bh(x)-1}-1) + 1 = 2^{bh(x)}-1$，即节点 $x$ 所包含的节点至少为 $2^{bh(x)}$-1。因此，原命题成立。
  - 结合①、②，得出：“高度为 $h$ 的红黑树，它包含的黑色节点个数至少为 $2^{bh(x)}$-1个”，因此，“一棵含有 $N$ 个节点的红黑树的高度至多为 $2log(N+1)$”。
上述定理说明：一棵 $N$ 个节点的红黑树始终能保持 $logN$ 的高度，故红黑树的各操作时间复杂度最坏为 $O(logN)$，红黑树的搜索时间复杂度为：$logN$。

旋转

当对红黑树进行插入和删除等操作时，对树做了修改可能会破坏红黑树的性质。为了继续保持红黑树的性质，可以通过对树进行相关的旋转操作（修改树的指针结构），以及对节点进行重新着色（修改树中某些节点的颜色），来达到对红黑树进行插入或删除等操作后继续保持它的性质 $\Longrightarrow$ 平衡的目的。
如上图所示，从左图到右图的过程为左旋，反之为右旋。旋转前后 $x$、$y$ 与三棵子树 $\alpha$、$\beta$、$\gamma$ 之间的大小关系均满足红黑树的搜索性质：$\alpha \lt x \lt \beta \lt y \lt \gamma$
左旋转：以 $y$ 节点为中心，将 $x$、$y$ 之间的轴（蓝色箭头）左旋（逆时针旋转），这使得 $y$ 称为该子树的新根；对 $x$ 进行左旋，意味着将 $x$ 变成一个左节点，显然是新根（即原本 $x$ 的右孩子 $y$）的左节点。

//输入：root为树的根节点，x与x的右子节点为待左旋的节点
//输出：旋转后的树结构
Left-Rotate(root, x)
  // 前提
  y = x->right
  
  // 将β设为x的右孩子
  x->right = y->left
  // 将β的父亲设为x
  if(NULL != y->left)
    y->left->parent = x
  
  // 情况1：x的父节点为空，即x原先为根节点，将y设为根节点
  if(NULL == x->parent)
    root = y
  // 情况2：子树的根x原先是它的父亲的左孩子，将y设为x的父亲的左孩子
  else if(x == x->parent->left)
    x->parent->left = y
  // 情况3：子树的根x原先是它的父亲的右孩子，将y设为x的父亲的右孩子
  else
    x->parent->right = y
   
  // 将x设为y的左孩子
  y->left = x
  // 将x的父节点设为y
  x->parent = y

右旋转

//输入：root为树的根节点，y与y的左子节点为待右旋的节点
//输出：旋转后的树结构
Right-Rotate(root, y)
  // 前提
  x = y->left
 
  // 将β设为y的左孩子
  y->left = x->right
  // 将β的父亲设为x
  if(NULL != x->right)
    x->right->parent = y
 
  // 情况1：y的父节点为空，即y原先为根节点，将x设为根节点
  if(NULL == y->parent)
    root = x
  // 情况2：子树的根y原先是它的父亲的左孩子，将x设为y的父亲的左孩子
  else if(y == y->parent->left)
    y->parent->left = x
  // 情况3：子树的根y原先是它的父亲的右孩子，将x设为y的父亲的右孩子
  else
    x->parent->right = y
 
  // 将y设为x的右孩子
  x->right = y
  // 将y的父节点设为x
  y->parent = x

一棵红黑树在经过左旋和右旋之后，树的搜索性质（二叉查找树性质）保持不变，但树的红黑性质则被破坏了，因此需要通过重新着色来恢复树的红黑性质。

插入

　将一个节点插入到红黑树中，需要执行哪些步骤呢？首先，将红黑树当做一棵二叉查找树，将节点插入；然后，将节点着色为红色；最后，通过旋转和重新着色等方法来修正该树，使之重新成为一棵红黑树。

将红黑树当做一棵二叉查找树，将节点插入。
- 无论是左旋还是右旋，若旋转之前这棵树是一棵二叉查找树，旋转之后它一定还是二叉查找树；任何的旋转和重新着色操作，都不会改变它仍然是一棵二叉查找树的事实。
- 红黑树本身就是一棵二叉查找树，将节点插入后，该树仍然是一棵二叉查找树，即树的键值仍然是有序的。
将插入的节点着色为“红色”。为什么着色成红色，而不是黑色呢？因为将着色为“红色”，不会违背红黑树性质⑤：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点；少违背一条特性，就意味着我们需要处理的情况越少，接下来只需要使其满足其它性质即可。

// root为红黑树的树根，z为要插入的新节点
RB-Insert(root, z)
  // 新建节点y，将y设为空节点
  y = NULL;
  // 设红黑树的根节点为x
  x = root;
 
  // 找出要插入新节点z在二叉树中的位置y
  while(NULL != x)
    y = x;
    if(z->key < x->key)
      x = x->left;
    else
      x = x->right;
 
  // 设z的父亲为y
  z->parent = y;
  // 情况1：y是空节点，将z设为根
  if(NULL == y)
    root = z;
  // 情况2：z设为y的左孩子
  else if(z->key < y->key)
    y->left = z;
  // 情况3：z设为y的右孩子
  else
    y->right = z;
 
  // z的左右孩子设为空格
  z->left = NULL;
  z->right = NULL;
  // 至此，已经完成将新节点z插入到二叉树中
 
  // 将z着色为“红色”
  z->color = RED;
  // 通过RB-Insert-Fixup对红黑树的节点进行颜色修改以及旋转，让树仍然是一棵红黑树
  RB-Insert-Fixup(root, z);

接下来的问题就是：想方设法地旋转以及重新着色，是这棵树重新称为一棵红黑树！

通过一系列的旋转或重新着色操作，使之重新成为一棵红黑树。
- 将插入节点着色为“红色”之后，不会违背性质⑤，那它到底会违背哪些性质呢？
  - 对于性质①，因为已经将它涂成红色了，显然不会违背；
  - 对于性质②，在上面步骤中我们将红黑树当做二叉查找树，然后执行插入操作；根据二叉查找树的特点，除非是根节点，插入操作不会改变根节点，所以，根节点仍然是黑色，除非插入的就是根节点；
  - 对于性质③，显然不会违背，这里的叶子节点是指空叶子节点，插入非空节点（其左右空叶子节点初始化即为黑色的）并不会对它们造成影响；
  - 对于性质④，很有可能违背！接下来是想办法使这棵树满足性质④，将树重新构造成红黑树。
- 根据被插入节点 $N$ 的父节点的情况，可以划分为以下三类情况处理：
  - 第一类：被插入的节点是根节点 $\Longrightarrow$ 直接把新节点涂为黑色
  - 第二类：被插入节点的父节点是黑色节点 $\Longrightarrow$ 新节点被插入后，仍然是红黑树
  - 第三类：被插入节点的父节点是红色节点 $\Longrightarrow$ 显然与性质⑤冲突，这种情况下，新节点一定存在非空祖父节点（肯定有黑色的节点作为父节点的父节点）；新节点也一定存在叔叔节点，即使叔叔节点为空叶子节点，其本身也是黑色节点，视之为存在。对于这类情况，需要依据“叔叔节点的情况”，进一步划分为一下三种情况（这三种情况可能存在一定转换关系）。
    - Case 1：叔叔节点 $U$ 是红色节点
      
      $\quad$处理策略：
      1. 将父节点 $P$ 设为黑色节点；
      2. 将叔叔节点 $U$ 设为黑色节点；
      3. 将祖父节点 $G$ 设为红色节点；
      4. 将祖父节点设为“当前节点”$N$，之后继续对“当前节点”进行操作。
    - Case 2：叔叔节点 $14$ 是黑色节点，且当前节点 $N$ 是右孩子
      
      $\quad$处理策略：
      1. 将父节点 $2$ 作为新的“当前节点”$N$；
      2. 以新的“当前节点”$N$ 为支点进行左旋。
    - Case 3：叔叔节点 $14$ 是黑色节点，且当前节点 $N$ 是左孩子
      
      $\quad$处理策略：
      1. 将父节点 $7$ 设为黑色节点；
      2. 将祖父节点 $11$ 设为红色节点；
      3. 以祖父节点 $11$ 为支点进行右旋。

// root为红黑树的树根，z为要插入的新节点
RB-Insert-Fixup(root, z)
  // 若当前节点z的父节点是红色，则进行以下处理
  while(RED == z->parent->color)
    // 若z的父节点是z的祖父节点的左孩子
    if(z->parent == z->parent->parent->left)
      // 将y设置为z的叔叔节点（z的祖父节点的右孩子）
      y = z->parent->parent->right;
 
      // Case 1
      if(RED == y->color)
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      // Case 2
      else if(z == z->parent->right)
        Left-Rotate(root, z);
      // Case 3
      else
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        Right-Rotate(root, z->parent->parent);
    // z在父节点是z的祖父节点的右孩子，与左子树原理相同，将right与left互换即可
    else
      // 将y设置为z的叔叔节点（z的祖父节点的左孩子）
      y = z->parent->parent->left;
 
      // Case 1
      if(RED == y->color)
        z->parent->color = BLACK;
        y->color = BLACK;
        z->parent->parent->color = RED;
        z = z->parent->parent;
      // Case 2
      else if(z == z->parent->left)
        Right-Rotate(root, z);
      // Case 3
      else
        z->parent->color = BLACK;
        z->parent->parent->color = RED;
        Left-Rotate(root, z->parent->parent);
  // 被插入的节点是根节点
  root->color = BLACK;

删除

　将红黑树内的某一个节点删除，需要执行的操作依次是：首先将红黑树当做一棵二叉查找树，将该节点从二叉查找树中删除；然后，通过“旋转和重新着色”等一系列来修正该树，使之重新成为一棵红黑树。

将红黑树当做一棵二叉查找树，将节点删除，这和在常规二叉查找树中删除节点的方法一样，分3种情况：
- ①被删除节点没有儿子，即为叶子节点，那么，直接将该节点删除；
- ②被删除节点只有一个儿子，那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置；
- ③被删除节点有两个儿子，那么，先找出它的后继节点，然后把该后继节点的“内容”复制给该节点的“内容”，之后删除该后继节点。
  - 该后继节点相当于替身，在将后继节点的“内容”赋值给被删除节点之后，再将后继节点删除，这样就巧妙地将问题转换为“删除后继节点”的情况了；
  - 在被删除节点有两个非空子节点的情况下，它的后继节点不可能是双子非空的（至少左孩子为空，否则显然不可能是后继节点）：若没有儿子，则按情况①进行处理；若只有一个儿子，则按情况②进行处理。

RB-Delete(root, z)
  // 若z的左孩子或右孩子为空
  if(NULL==z->left || NULL==z->right)
    y = z;
  // 将z的后继节点赋值给y
  else
    y = Tree-Successor(z);
 
  // y至少一个孩子为空
  if(NULL != y->left)
    x = y->left;
  else
    x = y->right;
 
  // 将y的父节点设置为x的父节点
  x->parent = y->parent;
 
  // 情况1：y的父节点为空，则设置x为根节点
  if(NULL == y->parent)
    root = x;
  // 情况2：y是它父节点的左孩子，则设置x为y的父节点的左孩子
  else if(y == y>parent->left)
    y->parent->left = x;
  // 情况3：y是它父节点的右孩子，则设置x为y的父节点的右孩子
  else
    y->parent->right = x;
 
  // 将z的后继节点y的值赋值给z，这里只拷贝z的值给y，而没有拷贝z的颜色!!!
  if(y != z)
    z->key = y->key;
    //copy y's satelite date into z;
 
  // 若y为黑色节点
  if(BLACK == y->color)
    RB-Delete-Fixup(root, x);

上一步中删除节点之后，可能会违背红黑树的性质，所以需要通过“旋转和重新着色”来修正该树，使之重新成为一棵红黑树。
- 由上面的算法，我们知道：删除节点 $y$ 之后，$x$ 占据了原本节点 $y$ 的位置。既然删除 $y$（$y$ 是黑色节点），意味着减少一个黑色节点，那么，再在该位置上增加一个黑色节点即可，即假设“$x$ 包含一个额外的黑色节点”（$x$ 最终需要变成一个黑色节点），就正好弥补了“删除 $y$ 所丢失的黑色节点”，也就不会违反性质⑤；
  - 现在，$x$ 不仅包含它原本的颜色属性，还包含一个额外的颜色，即 $x$ 的颜色属性是“红+黑”或者“黑+黑”，它违反了性质①；我们面临的问题，由解决“违反性质②、性质④、性质⑤”转换成了解决违反性质①、性质②、性质④”；
- 解决的思想是：将 $x$ 所包含的额外的黑色属性不断沿树上移（向根方向移动：Case 2），直到出现下面的情况：
  - 第一类：$x$ 是“红+黑”节点，此时，直接将 $x$ 设为一个“黑”节点即可，红黑树的性质全部恢复；
    - 如果删除的节点是红色节点，则删除后，树依然能够保持红黑性？？？（错误的命题？）
      1. 树中各节点的黑高度不会发生变化？可能会发生变化；
      2. 不存在父子节点都是红色节点的情况；
      3. 根依然是黑色节点。
  - 第二类：$x$是“黑+黑”节点且 $x$ 是根，此时，将 $x$ 设为一个“黑”节点即可，红黑树的性质全部恢复；
  - 第三类：$x$是“黑+黑”节点但 $x$ 不是根，这种情况又可以划分为以下 4 种情况：
    - Case 1：$A$ 是 “黑+黑”节点，$A$ 的兄弟节点 $D$ 是红色（此时 $A$ 的父节点 $B$ 和 $A$ 的兄弟节点的子节点 $C$、$E$ 都是黑色）
      
      $\quad$处理策略：
      1. 将 $A$ 的兄弟节点 $D$ 设为黑色节点；
      2. 将 $A$ 的父节点 $B$ 设为红色节点；
      3. 对 $A$ 的父节点 $B$ 进行左旋（BD为轴）；
      4. 左旋后，由于 $A$ 的兄弟节点发生了变化，需要更新 $A$ 的兄弟节点（由 $D$ 变成 $C$），继续进行后续处理（Case 1 转换为 Case 2、Case 3 或 Case 4）。
    - Case 2：$A$ 是 “黑+黑”节点，$A$ 的兄弟节点 $D$ 是黑色，$A$ 的兄弟节点的两个孩子 $C$、$E$ 都是黑色
      
      $\quad$处理策略：
      1. 将兄弟节点 $D$ 设为红色节点；
      2. 将父节点 $B$ 设为新的“当前节点”$N$，之后继续对“当前节点”进行操作。
    - Case 3：$A$ 是 “黑+黑”节点，$A$ 的兄弟节点 $D$ 是黑色；$A$ 的兄弟节点的左孩子 $C$ 是红色节点、右孩子 $E$ 是黑色节点
      
      $\quad$处理策略：
      1. 将兄弟节点 $D$ 的左孩子 $C$ 设为黑色节点；
      2. 将兄弟节点 $D$ 设为红色节点；
      3. 对兄弟节点 $D$ 进行右旋；
      4. 右旋后，需要更新 $A$ 的兄弟节点（由 $D$ 变成 $C$），继续进行后续处理（Case 3 转换为 Case 4）。
    - Case 4：$A$ 是 “黑+黑”节点，$A$ 的兄弟节点 $D$ 是黑色；$A$ 的兄弟节点的右孩子 $E$ 是红色节点、左孩子 $C$ 可以是任意颜色
      
      $\quad$处理策略：
      1. 将父节点 $B$ 的颜色赋值给兄弟节点 $D$；
      2. 将父节点 $B$ 设为黑色节点；
      3. 将兄弟节点 $D$ 的右孩子 $E$ 设为黑色节点；
      4. 对父节点 $B$ 进行左旋；
      5. 设置 $x$ 设为根节点，就可以跳出while循环，即完成了全部处理。
- 上述Case 1-4都只是树的局部，并非树的整体部分；且删除后红黑树恢复Case 3、Case 4在经过上面的调整后，还要继续调整直至重新恢复平衡。

// x：被删除节点位置的替换节点
RB-Delete-Fixup(root, x)
  // 删除节点x是根节点或删除节点x是红色节点，红黑树的性质都能保持!!!
  while(x!=root && BLACK==x->color)
    // x是它父节点的左孩子，w为x叔叔，即父节点的右孩子
    if(x == x->parent->left)
      w = x->parent->right;
      // Case 1
      if(RED == w->color)
        // x的兄弟节点设为黑色
        w->color = BLACK;
        // x的父节点设为红色
        x->parent->color = RED;
        // 对x的父节点进行左旋
        Left-Rotate(root, x->parent);
        // 左旋后，重新设置x的兄弟节点
        w = x->parent->right;
      // Case 1 ==> Case 2、3、4
      // Case 2
      if(BLACK==w->left->color && BLACK==w->right->color)
        // x的兄弟节点设为红色
        w->color = RED;
        // 设置x的父节点为新一轮迭代的x节点，向上转移
        x = x->parent;
      // Case 3：x的兄弟节点左孩子是红色，右孩子是黑色
      else if(BLACK==w->right->color)
        // x的兄弟节点的左孩子设为黑色
        w->left->color = BLACK;
        // x的兄弟节点设为红色
        w->color = RED;
        // 对x的兄弟节点进行右旋
        Right-Rotate(root, w);
        // 右旋后，重新设置x的兄弟节点，进行下一轮迭代 ==> Case 4
        w = x->parent->right;
      // Case 4：z的兄弟节点右孩子是红色，左孩子任意颜色
      else
        // 将x父节点的颜色赋值给x的兄弟节点
        w->color = x->parent->color;
        // 将x父节点设为黑色
        x->parent->color = BLACK;
        // 将x兄弟节点的右孩子设为黑色
        w->right->color = BLACK;
        // 对x的父节点进行左旋
        Left-Rotate(root, x->parent);
        // 设置x为根节点，退出while循环
        x = root;
    else
      // z是父节点的右孩子，与左子树原理相同，将right与left互换即可
      w = x->parent->left;
      // Case 1
      if(RED == w->color)
        // x的兄弟节点设为黑色
        w->color = BLACK;
        // x的父节点设为红色
        x->parent->color = RED;
        // 对x的父节点进行右旋
        Right-Rotate(root, x->parent);
        // 右旋后，重新设置x的兄弟节点
        w = x->parent->left;
      // Case 1 ==> Case 2、3、4
      // Case 2
      if(BLACK==w->left->color && BLACK==w->right->color)
        // x的兄弟节点设为红色
        w->color = RED;
        // 设置x的父节点为新一轮迭代的x节点，向上转移
        x = x->parent;
      // Case 3：x的兄弟节点右孩子是红色，左孩子是黑色
      else if(BLACK==w->left->color)
        // x的兄弟节点的右孩子设为黑色
        w->right->color = BLACK;
        // x的兄弟节点设为红色
        w->color = RED;
        // 对x的兄弟节点进行左旋
        Left-Rotate(root, w);
        // 左旋后，重新设置x的兄弟节点，进行下一轮迭代 ==> Case 4
        w = x->parent->right;
      // Case 4：z的兄弟节点左孩子是红色，右孩子任意颜色
      else
        // 将x父节点的颜色赋值给x的兄弟节点
        w->color = x->parent->color;
        // 将x父节点设为黑色
        x->parent->color = BLACK;
        // 将x兄弟节点的左孩子设为黑色
        w->left->color = BLACK;
        // 对x的父节点进行右旋
        Right-Rotate(root, x->parent);
        // 设置x为根节点，退出while循环
        x = root;
 
  x->color = BLACK;

References

本文标题:算法设计与分析[0022] BST（二叉查找树）和 R-B Tree（红黑树）

文章作者:Gary

发布时间:2017-07-08, 12:02:22

最后更新:2020-03-28, 12:37:22

原始链接:http://durant35.github.io/2017/07/08/Algorithms_BST$R-B Tree/